package algorithm.morris;

import algorithm.morris.MorrisTraversal.Node;

import java.util.Timer;
import java.util.TimerTask;

public class MinHeight {


    public static int minHeight(Node head) {
        if (head == null)
            return -1;
        return process(head);
    }

    public static int process(Node head) {
        if (head == null)
            return 0;
        int height1;
        int height2;
        height1 = process(head.left);
        height2 = process(head.right);
        int min = height1 == 0 ? (height2 == 0 ? 1 : height2 + 1) :
                (height2 == 0 ? height1 + 1 : Math.min(height1, height2) + 1);
        return min;
    }


    //整体思路：当前节点刚来到循环的时候还没有更新信息，首先需要对信息进行更新

    // 存在的问题：如果走节点的右子树会存在返回回去的情况，对更新level信息存在问题。

    //判断是不是叶节点也需要在第二次回到节点时，将最右节点恢复回去后再进行判断。
    public static int minHeight2(Node head) {
        if(head == null)
            return -1;
        Node cur = head;
        Node mostRight;
        int level = 0;
        int min = Integer.MAX_VALUE;
        while (cur != null) {
            System.out.println(level);
            if (cur.left != null) {
                mostRight = cur.left;
                int rightBoardSize = 1;
                while(mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                    rightBoardSize++;
                }
                //第一次来到当前节点，说明不是由下面的节点返回回来的，肯定是由上面节点遍历下来的，对当前层数进行更新直接+1
                if(mostRight.right == null){
                    level++;
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{//第二次来到当前节点，说明是由下面的节点返回回来的，level需要减去左子树右边界的大小
                    if(mostRight.left == null)
                        min = Math.min(min, level);
                    level = level - rightBoardSize;
//                    System.out.println(level);
                    mostRight.right = null;
                }
            }else{//左节点为空，说明当前节点只会遍历一次，不存在跳回来的可能，肯定是由上面节点遍历下来的，level直接+1
                level++;
//                System.out.println(level);
            }
            cur = cur.right;
        }

        cur = head;
        while (cur.right != null){
            cur = cur.right;
        }
        if(cur.left == null)
            min = Math.min(min, level);
        return min;
    }

    // for test
    public static Node generateRandomBST(int maxLevel, int maxValue) {
        return generate(1, maxLevel, maxValue);
    }

    // for test
    public static Node generate(int level, int maxLevel, int maxValue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }

    public static void main(String[] args) {
//        int treeLevel = 7;
//        int nodeMaxValue = 5;
//        int testTimes = 100000;
//        System.out.println("test begin");
//        for (int i = 0; i < testTimes; i++) {
//            Node head = generateRandomBST(treeLevel, nodeMaxValue);
//            int ans1 = minHeight(head);
//            int ans2 = minHeight2(head);
//            if (ans1 != ans2) {
//                System.out.println("Oops!");
//            }
//        }
//        System.out.println("test finish!");
        Node head = new Node(4);
        head.left = new Node(2);
        head.right = new Node(6);
        head.left.left = new Node(1);
        head.left.right = new Node(3);
        head.right.left = new Node(5);
        head.right.right = new Node(7);
        int i = minHeight2(head);
//        System.out.println(i);
        Timer timer = new Timer();
        TimerTask m = new TimerTask() {
            @Override
            public void run() {

            }
        };

    }
}
